﻿//Write a program that finds all prime numbers in the range [1...10 000 000].
//Use the sieve of Eratosthenes algorithm (find it in Wikipedia).


using System;

public class PrimeNumbersWithSieveOfEratosthenes
{
    public static void Main()
    {
        Console.WriteLine("Enter integer");
        int integer = int.Parse(Console.ReadLine());
        bool[] array = new bool[integer];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = true;
        }
        int sqrt = (int)Math.Sqrt(integer);
        for (int i = 2; i < sqrt; i++)
        {
            if (array[i] == true)
            {
                for (int j = i * i; j < integer; j += i)
                {
                    array[j] = false;
                }
            }
        }

        for (int i = 0; i < array.Length; i++)
        {
            if (array[i] == true)
            {
                if (i == 0)
                {
                    Console.Write("{{{0}, ", i);
                }
                else if (i == array.Length - 1)
                {
                    Console.Write("{0}}}\n", i);
                }
                else
                {
                    Console.Write("{0}, ", i);
                }
            }
        }

        Console.WriteLine();
    }
}